<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>
<body>
  <script>

// function charu(arr) {
//   const len = arr.length
//   for(let i=1; i < len; i++ ) {
//     const cur = arr[i]
//     let j
//     for(j = i-1; j>=0; j-- ) {
//       if( arr[j] > cur ) {
//         arr[j+1] = arr[j]
//       }else{
//         break
//       }
//     }
//     arr[j+1] = cur
//   }
//   return arr
// }
// console.log(charu([1, 0, 3, 4, 5, -6, 7, 8, 9, 10]))


// function quickSort(arr) {
//   if(arr.length<=1) return arr
//   console.log(arr.length/2)
//   const pivotIndex = Math.floor(arr.length/2)
//   const pivot = arr.splice(pivotIndex, 1)
  
//   let left = []
//   let right = []
//   for(let i=0; i< arr.length; i++) {
//     if(arr[i] > pivot) {
//       right.push(arr[i])
//     }else{
//       left.push(arr[i])
//     }
//   }
//   return [...quickSort(left), ...pivot, ...quickSort(right)]
// }

function quickSort(arr) {
  const len = arr.length-1
  if(len<=0) return arr
  const middleIndex = Math.floor(len/2)
  const leftArr = []
  const rightArr = []
  const middle = arr.splice(middleIndex, 1)
  // const rightArr = []
  for(let i=0; i <= arr.length; i++) {
    if(arr[i] <= middle) leftArr.push(arr[i])
    if(arr[i] > middle) rightArr.push(arr[i])
  }
  return [...quickSort(leftArr), ...middle, ...quickSort(rightArr)]
}

console.log(quickSort([2,3,567,34,34,32,65,87,9,89,54,23,32,43,65,9,0,7,5,23,1]))
console.log(quickSort([1, 0, 3, 4, 5, -6, 7, 8, 9, 10]))
  </script>
</body>
</html>